package huisu;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Set;

public class Permutation {

	public static void main(String[] args) {
		// Permutation pp = new Permutation();
		// int[] nums = new int[]{1,2,1};
		// List<List<Integer>> list = pp.permuteUnique2(nums);
		// for (List<Integer> list2 : list) {
		// System.out.println(list2);
		// }

		String[] words = { "x", "f", "v", "kvxmfmkvk", "kv", "m", "m" };

		// HashMap<String, Integer> map = new HashMap<>();
		// for(int i = 0; i < words.length; i++){
		// map.put(words[i], map.getOrDefault(words[i], 0) + 1);
		// }
		Arrays.sort(words);
		boolean[] used = new boolean[words.length];
		getStringPermWithRepeat(0, words, new StringBuilder(),
				new ArrayList<String>(), used);
	}

	// 给定nums，求排列
	public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (nums == null || nums.length <= 0) {
			return result;
		}
		// 同样是采用回溯的方式来做
		List<Integer> temp = new ArrayList<>();
		backtrack(result, temp, nums);
		return result;
	}

	public void backtrack(List<List<Integer>> result, List<Integer> temp,
			int[] nums) {
		if (temp.size() == nums.length) {
			result.add(new ArrayList<>(temp));
		}
		for (int i = 0; i < nums.length; i++) {
			// 排列，如果已经加入了，就不再加入
			if (temp.contains(nums[i])) {
				continue;
			}
			temp.add(nums[i]);
			backtrack(result, temp, nums);
			temp.remove(temp.size() - 1);
		}
	}

	/**
	 * have't to see ,forgein people write clarify and explain well
	 * BackTracking. If the nums array cannot be changed (i.e. cannot sort the
	 * array), than we may need to keep some thing to record which number have
	 * been used. In this question, we keep a hashmap with the numbers in the
	 * nums as the key and the number of their appearance as value So each time
	 * we used a number, we substract its appearance by 1 and searching down by
	 * recursion. So we only use the number with appearance greater than 0. Once
	 * we reached the length of the nums, we add current result into the ret
	 * list. And by the time the recursion returns, we backtrack by adding back
	 * 1 to the appearance and remove the last number of current result. O(n! *
	 * n) time, O(n) space with consider the recursion stack. The recursion
	 * stack would consume O(n) space since the recutsion would be n-level in
	 * depth where n is the length of nums.
	 */
	// 有重复的元素时，比如[1, 1, 2]
	// 可是结果是超时，测试用例里面有一个8位数的，看来不能一个一个排列
	// 测试用例： [-1,2,-1,2,1,-1,2,1]
	// 这样子的排列会包含重复的序列
	// 比如 1 1 2 会出现两次
	public List<List<Integer>> permuteUnique(int[] nums) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (nums == null || nums.length <= 0) {
			return result;
		}
		HashMap<Integer, Integer> map = new HashMap<>();
		Integer times = 0;
		for (int i = 0; i < nums.length; i++) {
			if ((times = map.get(nums[i])) != null) {
				map.put(nums[i], times + 1);
			} else {
				map.put(nums[i], 1);
			}
		}
		List<Integer> list = new ArrayList<Integer>();
		backtrack(result, list, nums, map);
		return result;
	}

	public void backtrack(List<List<Integer>> result, List<Integer> list,
			int[] nums, HashMap<Integer, Integer> map) {
		// System.out.println("size: " + list.size());
		if (list.size() == nums.length) {
			// if(!result.contains(list)){
			// result.add(new ArrayList<Integer>(list));
			// }
			// and we would't judge if we already add this list
			result.add(new ArrayList<Integer>(list));
		}
		Integer times = 0;
		// 这样写会TLE
		// for(int i = 0; i < nums.length; i++){
		// //注意小于1表示没有该数字可以添加了
		// if( (times = map.get(nums[i])) < 1 && list.contains(nums[i])){
		// continue;
		// }
		// list.add(nums[i]);
		// map.put(nums[i], times - 1);
		// backtrack(result, list, nums, map);
		// map.put(nums[i], times);
		// list.remove(list.size() - 1);
		// }
		Set<Integer> set = map.keySet();
		for (Integer integer : set) {
			// 注意小于1表示没有该数字可以添加了
			// 这里可以写成
			if ((times = map.get(integer)) < 1) {
				continue;
			}
			// if( (times = map.get(integer)) < 1 && list.contains(integer)){
			// continue;
			// }
			list.add(integer);
			map.put(integer, times - 1);
			backtrack(result, list, nums, map);
			map.put(integer, times);
			list.remove(list.size() - 1);
		}
	}

	/**
	 * If we are allowed to sort the array, we could sort the array to let the
	 * same number cluster together. In this way, avoiding duplicates, which is
	 * to avoid the same number being the first number in the permutation, is
	 * simplified bacause we can judge is a number is the same as its previous
	 * one and if its previous one has been used. We keep a boolean array to
	 * store the numbers being used, whose values are false originally. Each
	 * time we use a number, we set its corresponding value in boolean array to
	 * be true. And we try further down in the recursion. Once the recursion
	 * returns, we backtrack by changing its corresponding boolean value to be
	 * false and remove it from the current result. O(n!) time, O(n) space.
	 */
	public List<List<Integer>> permuteUnique2(int[] nums) {
		List<List<Integer>> ret = new ArrayList<>();
		if (nums == null || nums.length == 0)
			return ret;
		Arrays.sort(nums);
		// 用于记录是否使用过
		boolean[] used = new boolean[nums.length];

		permuteHelper(nums, 0, ret, used, new ArrayList<Integer>());

		return ret;
	}

	private void permuteHelper(int[] nums, int len, List<List<Integer>> ret,
			boolean[] used, List<Integer> curr) {
		if (len == nums.length) {
			System.out.println(curr);
			ret.add(new ArrayList<Integer>(curr));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if (!used[i]) {
				System.out.println(curr);
				// 注意，如果后面的与前面的相同，那我们可以不使用
				if (i > 0) {
					System.out.println("length: " + len + " i: " + i + "   "
							+ used[i - 1]);
				}
				if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]) {
					continue;
				}
				used[i] = true;
				curr.add(nums[i]);
				permuteHelper(nums, len + 1, ret, used, curr);
				curr.remove(curr.size() - 1);
				used[i] = false;
			}
		}
	}

	// 求所有字符串的排列
	// 字符串中没有重复
	public static void getStringPerm(int curCount, String[] words,
			StringBuilder sb, List<String> list) {
		if (curCount == words.length) {
			System.out.println("the string" + sb.toString());
			return;
		}
		for (int i = 0; i < words.length; i++) {
			// 排列，如果已经加入了，就不再加入
			if (list.contains(words[i])) {
				continue;
			}
			StringBuilder temp = new StringBuilder(sb);
			sb.append(words[i]);
			// System.out.println("add string" + sb);
			list.add(words[i]);
			getStringPerm(curCount + 1, words, sb, list);
			sb = temp;
			list.remove(list.size() - 1);
		}
	}

	// 当字符串中有重复元素时
	// 包含重复的元素
	public static void getStringPermWithRepeat(int curCount, String[] words,
			StringBuilder sb, List<String> list, HashMap<String, Integer> map) {
		if (curCount == words.length) {
			System.out.println("the string" + sb.toString());
			return;
		}
		Integer times = 0;
		Set<String> set = map.keySet();
		for (String string : set) {
			// 注意小于1表示没有该字符串可以添加了
			// 这里可以写成
			if ((times = map.get(string)) < 1) {
				continue;
			}
			StringBuilder temp = new StringBuilder(sb);
			sb.append(string);
			list.add(string);
			map.put(string, times - 1);
			getStringPermWithRepeat(curCount + 1, words, sb, list, map);
			map.put(string, times);
			list.remove(list.size() - 1);
			sb = temp;
		}
	}

	public static void getStringPermWithRepeat(int curCount, String[] words,
			StringBuilder sb, List<String> list, boolean[] used) {
		if (curCount == words.length) {
			System.out.println("the string" + sb.toString());
			return;
		}
		for (int i = 0; i < words.length; i++) {
			if (!used[i]) {
				// 注意，如果后面的与前面的相同，那我们可以不使用
				if (i > 0 && words[i] == words[i - 1] && used[i - 1]) {
					continue;
				}
				StringBuilder temp = new StringBuilder(sb);
				sb.append(words[i]);
				used[i] = true;
				list.add(words[i]);
				getStringPermWithRepeat(curCount + 1, words, sb, list, used);
				list.remove(list.size() - 1);
				used[i] = false;
				sb = temp;
			}
		}
	}
}
